//
// Created by Administrator on 2023/10/12.
// 素数, 线性筛法
/*
 * 讲解
 * B站:【线性筛素数】 https://www.bilibili.com/video/BV1BV4y177b3/?share_source=copy_web&vd_source=039990b6433b5af9bd2905234cc47ac6
 * https://zhuanlan.zhihu.com/p/146418699
 * https://blog.csdn.net/GD_ONE/article/details/104660294
 *
 * https://oj.hterobot.com/?#/question/107719?order=ID&offset=0&limit=20&teamid&name=%E7%B4%A0%E6%95%B0&range=public
 * 21个测试用例:
 * 
 * https://www.luogu.com.cn/problem/P3912
 * 10个测试用例:
 * int, long long都一样
*/
// 有点问题 再研究 n太大就没结果

#include <iostream>

using namespace std;

int main()
{
    int n = 100;
//    n = 1740948; // out: 130971
//    n = 2115790; //out:156902
//    n=91571465;// out: 5302853
//    n = 65090061389;//out: 2728793966
//    cin>>n;
    bool isPrime[n + 1] = {0};
    for (int i = 2; i < n + 1; ++i)
    {
        isPrime[i] = 1;
    }
    int prime_num[n + 1];
    // 统计素数的个数
    int pindex = 0;
    for (int i = 2; i < n + 1; ++i)
    {
        if (isPrime[i])
        {
            // 当前素数存到素数数组中
            prime_num[pindex] = i;
            ++pindex;
        }
        // 筛选当前pindex长度的素数 并且往后筛选不超过总数要求n的
        for (int j = 0; j <= pindex && i*prime_num[j]<=n; ++j)
        {
            // 素数对应的倍数就不是素数了
            isPrime[i * prime_num[j]] = 0;
            // 对于(i*质数)这个合数来说,如果第一个遇到的质数能够整除的话
            // 那么这个质数就是(i*质数)的最小质因数,每个数只需要用最小质因数筛一次即可
            // 如: 2x6=12,之后是 3x6=18 因为6%2==0, so 6里边包含2
            // 2就是后边数字的最小质因数, 所以就不用继续循环,break即可
            //这次不筛掉18, 是因为18的最小质因数是2, 会在之后的2x9时筛掉18
            if(i% prime_num[j]==0)
                break;
        }
    }
    cout<<pindex;
    return 0;
}
